package club.xiaojiawei.array;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/17 16:06
 * @question 34.在排序数组中查找元素的第一个位置和最后一个位置
 * @description 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]
 */
public class SearchForFirstAndLast34 {

    public static void main(String[] args) {
        int[] arr={1,1,1,1,1,1,2,3,4,5,5,5,5,6,7,8,9,10,20,21,30,40,60,60,60,60,100,200};
        System.out.println(Arrays.toString(searchRange(arr, 5)));
        System.out.println(Arrays.toString(searchRange(arr, 35)));
        System.out.println(Arrays.toString(searchRange(arr, 300)));
        System.out.println(Arrays.toString(searchRange(arr, 60)));
        System.out.println(Arrays.toString(searchRange(arr, 1)));
        int[] arrs=null;
        System.out.println(Arrays.toString(searchRange(arrs, 60)));
        System.out.println(Arrays.toString(searchRange(null, 60)));
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] ints = new int[2];
        if (nums==null||nums.length==0||target<nums[0]||target>nums[nums.length-1]){
            ints[0]=-1;
            ints[1]=-1;
            return ints;
        }
        int length = nums.length;
        int left=0;
        int right= length-1;
        while (left<=right){
            int middle=(left+right)>>1;
//            有by zero的风险
//            int middle=left+(target-nums[left])*(right-left)/(nums[right]-nums[left]);
            if (target<nums[middle]){
                right=middle-1;
            }else if (target>nums[middle]){
                left=middle+1;
            }else {
                int first=middle;
                int last=middle;
                while (first-1>-1&&nums[first-1]==target){
                    first--;
                }
                while (last+1<length&&nums[last+1]==target){
                    last++;
                }
                ints[0]=first;
                ints[1]=last;
                return ints;
            }
        }
        ints[0]=-1;
        ints[1]=-1;
        return ints;
    }
}
